/*	Copyright (c) 2010 MIEM (http://miem.edu.ru/)
 *
 *	Authors:
 *		* Andrey Shtykovskiy    ( ashty@itas.miem.edu.ru      )
 *		* Edward Klyshinsky     ( klyshinsky@itas.miem.edu.ru )
 *		* Sergey R. Tumkovsky   ( srt@itas.miem.edu.ru        )
 *
 *	This file is part of MOAN (morphology analysis) software.
 *
 *	MOAN is free software: you can redistribute it and/or modify it 
 *	under the terms of the GNU General Public License as published 
 *	by the Free Software Foundation, either version 3 of the License, 
 *	or (at your option) any later version.
 *
 *	This library is distributed in the hope that it will be useful,
 *	but WITHOUT ANY WARRANTY; without even the implied warranty of
 *	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *	Lesser General Public License for more details.
 *
 *	You should have received a copy of the GNU General Public License 
 *	along with MOAN. If not, see http://www.gnu.org/licenses/.
 */

#ifndef __DICTIONARY_HPP_GUARD__
#define __DICTIONARY_HPP_GUARD__

#include <algorithm>
#include <iterator>

namespace moan {
	template< 
		typename _item_ty, 
		typename _parameter_collection_ty
			>
	class dictionary {
	private:
		//forward declaration
		struct _node;

	public:
		typedef _node node_type;
		typedef _item_ty item_type;
		typedef _parameter_collection_ty parameter_collection_type;

		dictionary();
		~dictionary();

		inline bool empty() {
			return (0 == _keys_count);
		}

		inline size_t size() const {
			return _keys_count;
		}

		template<typename _iterator_ty>
		inline void insert(_iterator_ty begin, _iterator_ty end, const parameter_collection_type& parameter) {
			_root = _insert_r(_root, begin, end, parameter);
		}

		template<typename _iterator_ty>
		inline bool search(_iterator_ty begin, _iterator_ty end, parameter_collection_type* parameter);

		inline node_type* root() const {
			return _root;
		}

	private:

		struct _node {
			item_type item;
			parameter_collection_type *parameter;

			_node *hi, *lo, *eq;

			_node(const item_type& i) 
				: item(i), parameter(NULL), 
				  hi(NULL), lo(NULL), eq(NULL) { }

			~_node() {
			
				delete parameter;
				parameter = NULL;

				delete hi;
				hi = NULL;

				delete lo;
				lo = NULL;

				delete eq;
				eq = NULL;
			}
		}; /* struct _node */

		template<typename _iterator_ty>
		_node* _insert_r(
			_node* node, 
			_iterator_ty begin, _iterator_ty end, 
			const parameter_collection_type& parameter			);

		template<typename _iterator_ty> 
		inline bool _key_in_tree(node_type *node, _iterator_ty begin, _iterator_ty end) {
			if(!node) {
				return false;
			}

			if( node->parameter && (begin==end) ) {
				return true;
			}

			return false;
		}
	
		size_t _keys_count;
		_node *_root;
	};

	template< 
		typename _item_ty, 
		typename _parameter_collection_ty 
			>
	dictionary<_item_ty, _parameter_collection_ty>
		::dictionary() 
			: _root(NULL), _keys_count(0) { }

	template< 
		typename _item_ty, 
		typename _parameter_collection_ty
			>
	dictionary<_item_ty, _parameter_collection_ty>
		::~dictionary() {
			//assert(_root); <-- not legal (empty dictionary 
			//				     will always have empty _root)

			delete _root;
			_root = NULL;
	}

	template< 
		typename _item_ty, 
		typename _parameter_collection_ty
			>
	template<typename _iterator_ty>
	typename dictionary<_item_ty, _parameter_collection_ty>::node_type*
	dictionary<_item_ty, _parameter_collection_ty>
		::_insert_r(_node* node, _iterator_ty begin, _iterator_ty end, const parameter_collection_type& parameter) {
		
	item_type item = (*begin);

			if(!node) {
				node = new _node(item);
			}

			if(item == node->item) {
				if( (begin + 1) == end ) { // Houston, we got a key's end
					if(!node->parameter) {
						node->parameter = new parameter_collection_type();
						++_keys_count;
					}

					std::copy(
						parameter.begin(), 
						parameter.end(), 
						std::back_inserter( *(node->parameter) ) );

				} else {  /* if( (begin + 1) == end ) */
					node->eq = _insert_r(node->eq, ++begin, end, parameter);
				}
			} else if (item < node->item) {
				node->lo = _insert_r(node->lo, begin, end, parameter);
			} else /* if(item > node->item) */ {
				node->hi = _insert_r(node->hi, begin, end, parameter);
			}

			return node;
	} /* _insert_r(_node* node, _iterator_ty begin, _iterator_ty end, const _parameter_ty& parameter) */


	template< 
		typename _item_ty, 
		typename _parameter_collection_ty 
			>
	template<typename _iterator_ty>
	bool
	dictionary<_item_ty, _parameter_collection_ty> 
		::search(_iterator_ty begin, _iterator_ty end, parameter_collection_type* parameter) {

			assert(parameter);
		
			node_type *node = _root;
			item_type item = (*begin);

			while( node ) {

				if( item == node->item ) {
					if( _key_in_tree(node, ++begin, end) )  {

						std::copy( 
							node->parameter->begin(), 
							node->parameter->end(), 
							std::back_inserter( *parameter ) );

						return true;
					}

					item = (*begin);
					node = node->eq;

				} else if ( item < node->item ) {
					node = node->lo;
				} else /* if ( item > node->item ) */ {
					node = node->hi;
				}
			}

			return false;

	} /* search(_iterator_ty begin, _iterator_ty end, parameter_collection_type* parameter) */

} /* namespace moan */

#endif /* __DICTIONARY_HPP_GUARD__ */